package leetcode.offer_two_special.tree;

import leetcode.tree.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 * <p>
 * BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
 * bSTIterator.next();    // 返回 3
 * bSTIterator.next();    // 返回 7
 * bSTIterator.hasNext(); // 返回 True
 * bSTIterator.next();    // 返回 9
 * bSTIterator.hasNext(); // 返回 True
 * bSTIterator.next();    // 返回 15
 * bSTIterator.hasNext(); // 返回 True
 * bSTIterator.next();    // 返回 20
 * bSTIterator.hasNext(); // 返回 False
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kTOapQ
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author mazouri
 * @create 2021-09-12 23:05
 */
public class BSTIterator {
//    TreeNode cur;
//    Stack<TreeNode> stack;
//
//    public BSTIterator(TreeNode root) {
//        this.cur = root;
//        stack = new Stack<>();
//    }
//
//    public int next() {
//        while (cur != null) {
//            stack.push(cur);
//            cur = cur.left;
//        }
//
//        cur = stack.pop();
//        int val = cur.val;
//        cur = cur.right;
//        return val;
//    }
//
//    public boolean hasNext() {
//        return cur != null || !stack.isEmpty();
//    }

    Queue<TreeNode> queue = new LinkedList<>();

    public BSTIterator(TreeNode root) {
        inorder(root);
    }

    private void inorder(TreeNode root) {
        if (root != null) {
            inorder(root.left);
            queue.offer(root);
            inorder(root.right);
        }
    }

    public int next() {
        return queue.poll().val;
    }

    public boolean hasNext() {
        return !queue.isEmpty();
    }
}
